{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Rectangle Area II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #segment-tree #array #ordered-set #line-sweep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #线段树 #数组 #有序集合 #扫描线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rectangleArea"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩形面积 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个轴对齐的二维数组&nbsp;<code>rectangles</code>&nbsp;。 对于&nbsp;<code>rectangle[i] = [x1, y1, x2, y2]</code>，其中（x1，y1）是矩形&nbsp;<code>i</code>&nbsp;左下角的坐标，<meta charset=\"UTF-8\" />&nbsp;<code>(x<sub>i1</sub>, y<sub>i1</sub>)</code>&nbsp;是该矩形 <strong>左下角</strong> 的坐标，<meta charset=\"UTF-8\" />&nbsp;<code>(x<sub>i2</sub>, y<sub>i2</sub>)</code>&nbsp;是该矩形&nbsp;<strong>右上角</strong> 的坐标。</p>\n",
    "\n",
    "<p>计算平面中所有&nbsp;<code>rectangles</code>&nbsp;所覆盖的 <strong>总面积 </strong>。任何被两个或多个矩形覆盖的区域应只计算 <strong>一次</strong> 。</p>\n",
    "\n",
    "<p>返回<em> <strong>总面积</strong> </em>。因为答案可能太大，返回<meta charset=\"UTF-8\" />&nbsp;<code>10<sup>9</sup>&nbsp;+ 7</code> 的&nbsp;<strong>模</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/06/rectangle_area_ii_pic.png\" style=\"height: 360px; width: 480px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>如图所示，三个矩形覆盖了总面积为 6 的区域。\n",
    "从(1,1)到(2,2)，绿色矩形和红色矩形重叠。\n",
    "从(1,0)到(2,3)，三个矩形都重叠。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rectangles = [[0,0,1000000000,1000000000]]\n",
    "<strong>输出：</strong>49\n",
    "<strong>解释：</strong>答案是 10<sup>18</sup> 对 (10<sup>9</sup> + 7) 取模的结果， 即 49 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= rectangles.length &lt;= 200</code></li>\n",
    "\t<li><code>rectanges[i].length = 4</code><meta charset=\"UTF-8\" /></li>\n",
    "\t<li><code>0 &lt;= x<sub>i1</sub>, y<sub>i1</sub>, x<sub>i2</sub>, y<sub>i2</sub>&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [rectangle-area-ii](https://leetcode.cn/problems/rectangle-area-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [rectangle-area-ii](https://leetcode.cn/problems/rectangle-area-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,2,2],[1,0,2,3],[1,0,3,1]]', '[[0,0,1000000000,1000000000]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        edges = set()\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            edges.add(x1)\n",
    "            edges.add(x2)\n",
    "        # rectangles.sort(key=lambda i: i[0])\n",
    "        edges_list = list(edges)\n",
    "        edges_list.sort()\n",
    "        for i in range(1, len(edges_list)):\n",
    "            height = 0\n",
    "            low = -1\n",
    "            high = -1\n",
    "            help = []\n",
    "            for rect in rectangles:\n",
    "                if rect[2] >= edges_list[i] and rect[0] <= edges_list[i - 1]:\n",
    "                    help.append((rect[1], rect[3]))\n",
    "            help.sort()\n",
    "            for l, h in help:\n",
    "                if l > high:\n",
    "                     height += high - low\n",
    "                     high, low = h, l\n",
    "                elif h > high:\n",
    "                    high = h\n",
    "            \n",
    "            height += high - low\n",
    "            res += height * (edges_list[i] - edges_list[i- 1]) % (10**9 + 7)\n",
    "        return res % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def func(self, left, right, rectangles):\n",
    "        arr = []\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            if x1 <= left and x2 >= right:\n",
    "                arr.append((y1, y2))\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "        arr.sort()\n",
    "        length = 0\n",
    "        start = arr[0][0]\n",
    "        end = arr[0][1]\n",
    "\n",
    "        for s, e in arr[1:]:\n",
    "            if s <= end:\n",
    "                end = max(end, e)\n",
    "            else:\n",
    "                length += end - start\n",
    "                start = s\n",
    "                end = e\n",
    "        length += end - start\n",
    "\n",
    "        return length * (right - left)\n",
    "\n",
    "        \n",
    "\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        MOD = int(1e9+7)\n",
    "        xs = []\n",
    "        for x1, _, x2, _ in rectangles:\n",
    "            xs.extend([x1, x2])\n",
    "        xs = list(set(xs))\n",
    "        xs.sort()\n",
    "        sz = len(xs)\n",
    "        res = 0\n",
    "        for i in range(1, sz):\n",
    "            res = (res + self.func(xs[i-1], xs[i], rectangles)) % MOD\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        hbound = set()\n",
    "        for rect in rectangles:\n",
    "            hbound.add(rect[1])\n",
    "            hbound.add(rect[3])\n",
    "        \n",
    "        hbound = sorted(hbound)\n",
    "        m = len(hbound)\n",
    "\n",
    "        seg = [0] * (m-1)\n",
    "\n",
    "        sweep = list()\n",
    "        for i, rect in enumerate(rectangles):\n",
    "            sweep.append((rect[0], i, 1))\n",
    "            sweep.append((rect[2], i, -1))\n",
    "        \n",
    "        sweep.sort()\n",
    "\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < len(sweep):\n",
    "            j = i\n",
    "            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(sweep):\n",
    "                break\n",
    "\n",
    "            for k in range(i, j+1):\n",
    "                _, idx, diff = sweep[k]\n",
    "                left, right = rectangles[idx][1], rectangles[idx][3]\n",
    "                for x in range(m - 1):\n",
    "                    if left <= hbound[x] and hbound[x + 1] <= right:\n",
    "                        seg[x] += diff\n",
    "            cover = 0\n",
    "            for k in range(m - 1):\n",
    "                if seg[k] > 0:\n",
    "                    cover += (hbound[k + 1] - hbound[k])\n",
    "            \n",
    "            ans += cover * (sweep[j + 1][0] - sweep[j][0])\n",
    "            i = j + 1\n",
    "\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        xs, ans = set(), 0\n",
    "        for x0, _, x1, _ in rectangles:\n",
    "            xs.add(x0)\n",
    "            xs.add(x1)\n",
    "        # 纵向x轴扫描线\n",
    "        for a, b in pairwise(sorted(xs)):\n",
    "            ys = [(y0, y1) for x0, y0, x1, y1 in rectangles if x0 <= a and b <= x1]\n",
    "            s = cur = 0\n",
    "            # 横向y轴扫描线\n",
    "            for c, d in sorted(ys, key=lambda x: (x[0], -x[1])):\n",
    "                if c > cur:\n",
    "                    s += d - c\n",
    "                elif d > cur:\n",
    "                    s += d - cur\n",
    "                cur = max(cur, d)\n",
    "            ans = (ans + s * (b - a)) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "\n",
    "        axis = set()\n",
    "        for rec in rectangles:\n",
    "            axis.add(rec[0])\n",
    "            axis.add(rec[2])\n",
    "        axis = sorted(list(axis))\n",
    "\n",
    "        ans = 0\n",
    "        n = len(axis)\n",
    "        for i in range(n - 1):\n",
    "            x1, x2 = axis[i], axis[i + 1]\n",
    "            width = x2 - x1\n",
    "            if not width:\n",
    "                continue\n",
    "            items = [[rec[1], rec[3]] for rec in rectangles if rec[0] < x2 and rec[2] > x1]\n",
    "            items.sort()\n",
    "            height = low = high = 0\n",
    "            for y1, y2 in items:\n",
    "                if y1 >= high:\n",
    "                    height += high - low\n",
    "                    low, high = y1, y2\n",
    "                else:\n",
    "                    low = low if low < y1 else y1\n",
    "                    high = high if high > y2 else y2\n",
    "            height += high - low\n",
    "            ans += width * height\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        xline = []\n",
    "        for rect in rectangles:\n",
    "            xline.append(rect[0])\n",
    "            xline.append(rect[2])\n",
    "        xline.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, len(xline)):\n",
    "            a, b = xline[i-1], xline[i]\n",
    "            width = b - a\n",
    "            if width == 0:\n",
    "                continue\n",
    "            lines = [(rect[1], rect[3]) for rect in rectangles if rect[0] <= a and b <= rect[2]]\n",
    "            lines.sort()\n",
    "            height, l, r = 0, -1, -1\n",
    "            for line in lines:\n",
    "                if line[0] > r:\n",
    "                    height += r - l\n",
    "                    l, r = line\n",
    "                elif line[1] > r:\n",
    "                    r = line[1]\n",
    "            height += r - l\n",
    "            ans += height * width\n",
    "        return ans % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "MOD = 1000000007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # 记录左右边界 [x1, x2]\n",
    "        boundaries = []\n",
    "        for rectangle in rectangles:\n",
    "            boundaries.append(rectangle[0])\n",
    "            boundaries.append(rectangle[2])\n",
    "\n",
    "        boundaries.sort()\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, len(boundaries)):\n",
    "            x1, x2 = boundaries[i - 1], boundaries[i]\n",
    "            # 子矩形的水平宽度\n",
    "            width = x2 - x1\n",
    "            if width == 0:\n",
    "                continue\n",
    "\n",
    "            # 找到所有覆盖当前子区间的矩形，并记录其上下边界\n",
    "            lines = list()\n",
    "            for rectangle in rectangles:\n",
    "                if rectangle[0] <= x1 and x2 <= rectangle[2]:\n",
    "                    lines.append((rectangle[1], rectangle[3]))\n",
    "\n",
    "            height = self.count_length(lines)\n",
    "\n",
    "            result += height * width\n",
    "            result %= MOD\n",
    "        return result\n",
    "\n",
    "    @classmethod\n",
    "    def count_length(cls, intervals: List[Tuple[int, int]]):\n",
    "        \"\"\" 计算所有子区间的长度，区间可能重叠\n",
    "        :param intervals:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        intervals.sort()\n",
    "        length, start, end = 0, -1, -1\n",
    "        for interval in intervals:\n",
    "            # 记录新的区间\n",
    "            if interval[0] > end:\n",
    "                # 累加区间长度\n",
    "                length += end - start\n",
    "                # 记录新的区间范围\n",
    "                start, end = interval\n",
    "            # 合并区间\n",
    "            elif interval[1] > end:\n",
    "                end = interval[1]\n",
    "        length += end - start\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\r\n",
    "        ps=set()\r\n",
    "        for rec in rectangles:\r\n",
    "            ps.add(rec[0])\r\n",
    "            ps.add(rec[2])\r\n",
    "        ps=sorted(ps)\r\n",
    "        ans=0\r\n",
    "        for i in range(len(ps)-1):\r\n",
    "            x1,x2=ps[i],ps[i+1]\r\n",
    "            lines=[]\r\n",
    "            for rec in rectangles:\r\n",
    "                if rec[0]<=x1 and rec[2]>=x2:\r\n",
    "                    lines.append([rec[1],rec[3]])\r\n",
    "            lines.sort()\r\n",
    "            l,r=-1,-1\r\n",
    "            height=0\r\n",
    "            for cur in lines:\r\n",
    "                if cur[0]>r:\r\n",
    "                    height+=r-l\r\n",
    "                    l,r=cur\r\n",
    "                elif cur[1]>r:\r\n",
    "                    r=cur[1]\r\n",
    "            height+=r-l\r\n",
    "            ans+=height*(x2-x1)\r\n",
    "            \r\n",
    "        return ans%(10**9+7)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        ps = []\n",
    "        ans = 0\n",
    "        for rec in rectangles: # 垂直线扫描\n",
    "            ps.append(rec[0])\n",
    "            ps.append(rec[2])\n",
    "        ps.sort()\n",
    "        n = len(ps)\n",
    "        for i in range(1, n):\n",
    "            a, b = ps[i - 1], ps[i]\n",
    "            width = b - a\n",
    "            if width == 0: continue\n",
    "            lines = [(line[1], line[3]) for line in rectangles if line[0] <= a and line[2] >= b]\n",
    "            lines.sort()\n",
    "            height, down, up = 0, -1, -1\n",
    "            for line in lines:\n",
    "                if line[0] > up:\n",
    "                    height += up - down\n",
    "                    down, up = line\n",
    "                elif line[1] > up:\n",
    "                    up = line[1]\n",
    "            height += up - down\n",
    "            ans += height * width\n",
    "        return ans % (10 ** 9 +7)\n",
    "            \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        high = []    #记录分段高度\n",
    "        for i in range(0,len(rectangles)):\n",
    "            high.append((rectangles[i][1],1,i))\n",
    "            high.append((rectangles[i][3],0,i))\n",
    "        high.sort()\n",
    "        T = []\n",
    "        for i in range(0,len(high)-1):\n",
    "            value = high[i+1][0] - high[i][0]\n",
    "            start_mode, start_rec = high[i][1], high[i][2]\n",
    "            end_mode, end_rec = high[i+1][1], high[i+1][2]\n",
    "            T.append((value, start_mode, start_rec,  end_mode, end_rec))\n",
    "        \n",
    "        res = 0\n",
    "        state = [0] * len(T)\n",
    "        query = []    #扫描查询\n",
    "        for i in range(0,len(rectangles)):\n",
    "            query.append((rectangles[i][0],1,i))\n",
    "            query.append((rectangles[i][2],0,i))\n",
    "        query.sort()\n",
    "        last = 0    #开始的扫描线\n",
    "        now_high = 0\n",
    "        for i in range(0,len(query)):\n",
    "            res += now_high * (query[i][0]-last)\n",
    "            judge = False\n",
    "            for j in range(0,len(T)):\n",
    "                if T[j][1] == 1 and T[j][2] == query[i][2]:\n",
    "                    judge = True\n",
    "                if judge:\n",
    "                    if query[i][1] == 1:\n",
    "                        state[j] += 1\n",
    "                    else:\n",
    "                        state[j] -= 1\n",
    "                if T[j][3] == 0 and T[j][4] == query[i][2]:\n",
    "                    judge = False\n",
    "            now_high = 0\n",
    "            for j in range(0,len(T)):\n",
    "                now_high += min(1,state[j]) * T[j][0] \n",
    "            last = query[i][0]\n",
    "        return res % (10**9+7)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        mod=10**9+7\n",
    "        xs=set()\n",
    "        # 统计相邻行坐标\n",
    "        for x1,y1,x2,y2 in rectangles:\n",
    "            xs.update([x1,x2])\n",
    "        \n",
    "        res=0\n",
    "        for l,r in pairwise(sorted(list(xs))):\n",
    "            # 将符合条件的列加入集合\n",
    "            ys=set()\n",
    "            for x1,y1,x2,y2 in rectangles:\n",
    "                if x1<=l and x2>=r:\n",
    "                    ys.add((y1,y2))\n",
    "            \n",
    "            ys=sorted(list(ys))\n",
    "            # 区间合并\n",
    "            stack=[]\n",
    "            for a,b in ys:\n",
    "                if stack and stack[-1][1]>=a:\n",
    "                    stack[-1][1]=max(stack[-1][1],b)\n",
    "                else:\n",
    "                    stack.append([a,b])\n",
    "            # 统计答案\n",
    "            for a,b in stack:\n",
    "                res+=(b-a)*(r-l)%mod\n",
    "                res%=mod\n",
    "        return res%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1000000007\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # 记录左右边界\n",
    "        boundaries = []\n",
    "        for rectangle in rectangles:\n",
    "            boundaries.append(rectangle[0])\n",
    "            boundaries.append(rectangle[2])\n",
    "\n",
    "        boundaries.sort()\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, len(boundaries)):\n",
    "            x1, x2 = boundaries[i - 1], boundaries[i]\n",
    "            width = x2 - x1\n",
    "            if width == 0:\n",
    "                continue\n",
    "                \n",
    "            lines = [(rectangle[1], rectangle[3]) for rectangle in rectangles if\n",
    "                     rectangle[0] <= x1 and x2 <= rectangle[2]]\n",
    "            lines.sort()\n",
    "            \n",
    "            height, left, right = 0, -1, -1\n",
    "            for line in lines:\n",
    "                if line[0] > right:\n",
    "                    height += right - left\n",
    "                    left, right = line\n",
    "                elif line[1] > right:\n",
    "                    right = line[1]\n",
    "                    \n",
    "            height += right - left\n",
    "            result += height * width\n",
    "        return result % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        hbound = set()\n",
    "        for rect in rectangles:\n",
    "            # 下边界\n",
    "            hbound.add(rect[1])\n",
    "            # 上边界\n",
    "            hbound.add(rect[3])\n",
    "        \n",
    "        hbound = sorted(hbound)\n",
    "        m = len(hbound)\n",
    "        # 「思路与算法部分」的 length 数组并不需要显式地存储下来\n",
    "        # length[i] 可以通过 hbound[i+1] - hbound[i] 得到\n",
    "        seg = [0] * (m - 1)\n",
    "\n",
    "        sweep = list()\n",
    "        for i, rect in enumerate(rectangles):\n",
    "            # 左边界\n",
    "            sweep.append((rect[0], i, 1))\n",
    "            # 右边界\n",
    "            sweep.append((rect[2], i, -1))\n",
    "        sweep.sort()\n",
    "\n",
    "        ans = i = 0\n",
    "        while i < len(sweep):\n",
    "            j = i\n",
    "            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(sweep):\n",
    "                break\n",
    "            \n",
    "            # 一次性地处理掉一批横坐标相同的左右边界\n",
    "            for k in range(i, j + 1):\n",
    "                _, idx, diff = sweep[k]\n",
    "                left, right = rectangles[idx][1], rectangles[idx][3]\n",
    "                for x in range(m - 1):\n",
    "                    if left <= hbound[x] and hbound[x + 1] <= right:\n",
    "                        seg[x] += diff\n",
    "            \n",
    "            cover = 0\n",
    "            for k in range(m - 1):\n",
    "                if seg[k] > 0:\n",
    "                    cover += (hbound[k + 1] - hbound[k])\n",
    "            ans += cover * (sweep[j + 1][0] - sweep[j][0])\n",
    "            i = j + 1\n",
    "        \n",
    "        return ans % (10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        ps = []\n",
    "        for info in rectangles:\n",
    "            ps.append(info[0])\n",
    "            ps.append(info[2])\n",
    "        ps.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, len(ps)):\n",
    "            a, b = ps[i-1], ps[i]\n",
    "            width = b - a\n",
    "            if width == 0:\n",
    "                continue\n",
    "            lines = [(info[1], info[3]) for info in rectangles\n",
    "                     if info[0] <= a and b <= info[2]]\n",
    "            lines.sort()\n",
    "            height, l, r = 0, -1, -1\n",
    "            for cur in lines:\n",
    "                if cur[0] > r:\n",
    "                    height += r - l\n",
    "                    l, r = cur\n",
    "                elif cur[1] > r:\n",
    "                    r = cur[1]\n",
    "            height += r - l\n",
    "            ans += height * width\n",
    "        return ans % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        #怎样快速计算一个点被哪些区间包围\n",
    "        #因为矩阵只有200个可以暴力遍历\n",
    "\n",
    "        mod = 10 **9 + 7\n",
    "        ans = 0\n",
    "        #捞出所有的横坐标，并且让横坐标排序\n",
    "        total = set()\n",
    "        for x1,y1,x2,y2 in rectangles:\n",
    "            total.add(x1)\n",
    "            total.add(x2)\n",
    "        \n",
    "        #根据x排序\n",
    "        total_x = [each for each in total]\n",
    "        total_x.sort()\n",
    "\n",
    "        #求相邻两个x之间矩形的面积\n",
    "        length = len(total_x)\n",
    "        ans = 0\n",
    "        for i in range(length - 1):\n",
    "            #看看这个起始的x所包含的高\n",
    "            heights = []\n",
    "            for x1,y1,x2,y2 in rectangles:\n",
    "                if x1 <= total_x[i] < x2:\n",
    "                    heights.append([y1,y2])\n",
    "            heights_merge = self.Merge(heights)\n",
    "\n",
    "            # print(heights_merge)\n",
    "            # print(total_x[i + 1], total_x[i])\n",
    "            ans += (total_x[i + 1] - total_x[i]) * sum([heights_merge[i][1] - heights_merge[i][0] for i in range(len(heights_merge)) ])\n",
    "            ans = ans % mod\n",
    "        return ans\n",
    "    #合并区间\n",
    "    def Merge(self, heights):\n",
    "        #根据heights[0]排序\n",
    "        heights.sort(key = lambda x:x[0])\n",
    "\n",
    "        ans = []\n",
    "        i = 0\n",
    "        start = 0\n",
    "        end  = 0\n",
    "        while i < len(heights):\n",
    "\n",
    "            start = heights[i][0]\n",
    "            end = heights[i][1]\n",
    "\n",
    "            i = i + 1\n",
    "            while i < len(heights) and heights[i][0] <= end:\n",
    "                end = max(end, heights[i][1])\n",
    "                i += 1\n",
    "            ans.append([start, end])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        sx, sy = set(), set()\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            sx.add(x1)\n",
    "            sx.add(x2)\n",
    "            sy.add(y1)\n",
    "            sy.add(y2)\n",
    "        sx, sy = list(sx), list(sy)\n",
    "        sx.sort()\n",
    "        sy.sort()\n",
    "        dx, dy = {sx[i]:i for i in range(len(sx))}, {sy[i]:i for i in range(len(sy))}\n",
    "        cover = [[0] * (len(sy) - 1) for _ in range(len(sx) - 1)]\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            xi1, xi2, yi1, yi2 = dx[x1], dx[x2], dy[y1], dy[y2]\n",
    "            for i in range(xi1, xi2):\n",
    "                for j in range(yi1, yi2):\n",
    "                    cover[i][j] = 1\n",
    "        ans = 0\n",
    "        for i in range(len(sx) - 1):\n",
    "            for j in range(len(sy) - 1):\n",
    "                if cover[i][j] == 1:\n",
    "                    ans += (sx[i + 1] - sx[i]) * (sy[j + 1]- sy[j])\n",
    "                    ans = ans % (10 ** 9 + 7)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # 根据 扫描线 和 离散化 的概念\n",
    "        # 我们要将 y 轴进行离散化处理 --- 将 y 轴离散化为 2n + 1 个部分\n",
    "        # 依据就是同样类似于扫描线，将矩形的上下两个边界用扫描线进行分割\n",
    "        # 这样分割出来的一段连续的点我们就可以用一个数来表示，这一段连续的点也只有两种情况\n",
    "        # 要么全部被覆盖，要么全部不被覆盖\n",
    "        # 然后我们再用扫描线 从左到右进行遍历 当遍历到左边界的时候，所有满足该扫描线覆盖的所有\n",
    "        # y上的部分都 + 1 处理 ， 当遇到一个右边界的时候，所有满足该扫描线覆盖的 y上的都 \n",
    "        # 进行 - 1 处理\n",
    "        # 每次都对相同的一组横坐标的数据进行处理\n",
    "\n",
    "        hbound = set() # 用集合存储，达到去重的效果\n",
    "        for rect in rectangles:\n",
    "            # 下边界\n",
    "            hbound.add(rect[1])\n",
    "            # 上边界\n",
    "            hbound.add(rect[3])\n",
    "\n",
    "        hbound = sorted(hbound)  # 排序 --- 转化成了列表\n",
    "        m = len(hbound)\n",
    "        # 「思路与算法部分」的 length 数组并不需要显式地存储下来\n",
    "        # length[i] 可以通过 hbound[i+1] - hbound[i] 得到\n",
    "\n",
    "        seg = [0] * (m - 1)  # 记录贡献值的  y 轴上的每个线段的贡献值\n",
    "\n",
    "        sweep = list()  # 存储的是左右边界的信息\n",
    "        for i, rect in enumerate(rectangles):\n",
    "            # 左边界 --- 左边界 是 + 1， 这里还没有加，只是标识一下这是左边界\n",
    "            sweep.append((rect[0], i, 1))  \n",
    "            # 右边界\n",
    "            sweep.append((rect[2], i, -1))\n",
    "        sweep.sort()   # 按照横坐标的大小进行排序\n",
    "\n",
    "        ans = i = 0\n",
    "        while i < len(sweep):\n",
    "            j = i\n",
    "            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(sweep):  # 此时表示的是最后一条边，后面就不可能构成矩形，break\n",
    "                break\n",
    "        \n",
    "            # 一次性地处理掉一批横坐标相同的左右边界\n",
    "            for k in range(i, j + 1):\n",
    "                _, idx, diff = sweep[k]\n",
    "                left, right = rectangles[idx][1], rectangles[idx][3]\n",
    "                for x in range(m - 1):\n",
    "                    if left <= hbound[x] and hbound[x + 1] <= right:\n",
    "                        seg[x] += diff\n",
    "            \n",
    "            cover = 0\n",
    "            for k in range(m - 1):\n",
    "                if seg[k] > 0:\n",
    "                    cover += (hbound[k+1] - hbound[k])\n",
    "            ans += cover * (sweep[j+1][0] - sweep[j][0])\n",
    "            i = j + 1\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "  def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "    cols = set()\n",
    "    for x1, y1, x2, y2 in rectangles:\n",
    "      cols.add(x1)\n",
    "      cols.add(x2)\n",
    "    cols = sorted(cols)\n",
    "    ans = 0\n",
    "    for i in range(1, len(cols)):\n",
    "      a, b = cols[i - 1], cols[i]\n",
    "      width = b - a\n",
    "      lines = [(y1, y2) for x1, y1, x2, y2 in rectangles if x1 <= a and b <= x2]\n",
    "      lines.sort()\n",
    "      height = 0\n",
    "      r = 0\n",
    "      for y1, y2 in lines:\n",
    "        if r >= y2: continue\n",
    "        height += y2 - max(y1, r)\n",
    "        r = y2\n",
    "      ans += width * height\n",
    "    return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        \n",
    "        pxs = []\n",
    "        for rect in rectangles:\n",
    "            pxs.append(rect[0])\n",
    "            pxs.append(rect[2])\n",
    "        \n",
    "        pxs.sort()\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for a, b in pairwise(pxs):\n",
    "            width = b - a\n",
    "            if width == 0:\n",
    "                continue\n",
    "            \n",
    "            lines = [\n",
    "                (rect[1], rect[3])\n",
    "                for rect in rectangles\n",
    "                if rect[0] <= a and b <= rect[2]\n",
    "            ]\n",
    "\n",
    "            lines.sort()\n",
    "\n",
    "            height = 0\n",
    "            le, ri = -1, -1\n",
    "\n",
    "            for cur in lines:\n",
    "                if cur[0] > ri:\n",
    "                    height += ri - le\n",
    "                    le, ri = cur\n",
    "                elif cur[1] > ri:\n",
    "                    ri = cur[1]\n",
    "\n",
    "            height += ri - le\n",
    "\n",
    "            res += height * width\n",
    "\n",
    "        return res % MOD \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        ans,xs=0,set()\n",
    "        MOD = int(1e9+7)\n",
    "        for x0,y0,x1,y1 in rectangles:\n",
    "            xs=xs|set({x0,x1})\n",
    "        xs = sorted(list(xs))\n",
    "        xs = [[xs[i],xs[i+1]] for i in range(len(xs)-1)]\n",
    "        for a,b in xs:\n",
    "            ys = [(y0,y1) for x0,y0,x1,y1 in rectangles if x0<=a and b<=x1]\n",
    "            s = cur = 0\n",
    "            for c,d in sorted(ys,key=lambda x:(x[0],-x[1])):\n",
    "                if c > cur:\n",
    "                    s += d - c\n",
    "                elif d > cur:\n",
    "                    s += d - cur\n",
    "                cur = max(cur, d)\n",
    "            ans = (ans + s * (b - a)) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        bound = set()\n",
    "        swp = []\n",
    "        for i, rec in enumerate(rectangles):\n",
    "            x1, y1, x2, y2 = rec\n",
    "            bound.add(y1)\n",
    "            bound.add(y2)\n",
    "            swp.append([x1, i, 1])\n",
    "            swp.append([x2, i, -1])\n",
    "        bound = list(bound)\n",
    "        bound.sort()\n",
    "        swp.sort()\n",
    "        n, m = len(swp), len(bound)\n",
    "        seg = [0] * (m - 1)\n",
    "        ans, i = 0, 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j + 1 < n and swp[j+1][0] == swp[j][0]:\n",
    "                j += 1\n",
    "            if j == n - 1:\n",
    "                i = j + 1\n",
    "                continue\n",
    "            for k in range(i, j+1):\n",
    "                rec = rectangles[swp[k][1]]\n",
    "                down, up = rec[1], rec[3]\n",
    "                for z in range(m-1):\n",
    "                    dd, uu = bound[z], bound[z+1]\n",
    "                    if down <= dd and up >= uu:\n",
    "                        seg[z] += swp[k][2]\n",
    "            for z in range(m-1):\n",
    "                if seg[z] > 0:\n",
    "                    ans += (bound[z+1] - bound[z]) * (swp[j+1][0] - swp[j][0])\n",
    "            i = j + 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        mod=10**9+7\n",
    "        xs=set()\n",
    "        for x1,y1,x2,y2 in rectangles:\n",
    "            xs.update([x1,x2])\n",
    "        \n",
    "        res=0\n",
    "        for l,r in pairwise(sorted(list(xs))):\n",
    "            print(l,r)\n",
    "            ys=set()\n",
    "            for x1,y1,x2,y2 in rectangles:\n",
    "                if x1<=l and x2>=r:\n",
    "                    ys.add((y1,y2))\n",
    "            \n",
    "            ys=sorted(list(ys))\n",
    "            print(ys)\n",
    "            stack=[]\n",
    "            for a,b in ys:\n",
    "                if stack and stack[-1][1]>=a:\n",
    "                    stack[-1][1]=max(stack[-1][1],b)\n",
    "                else:\n",
    "                    stack.append([a,b])\n",
    "            \n",
    "            for a,b in stack:\n",
    "                res+=(b-a)*(r-l)%mod\n",
    "                res%=mod\n",
    "        return res%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles):\n",
    "        \n",
    "        def merge(intervals):\n",
    "            ans = []\n",
    "            for beg, end in sorted(intervals):\n",
    "                if not ans or ans[-1][1] < beg:\n",
    "                    ans += [[beg, end]]\n",
    "                else:\n",
    "                    ans[-1][1] = max(ans[-1][1], end)\n",
    "            return sum(j-i for i,j in ans)\n",
    "        \n",
    "        sides_lft = [(x1,0,y1,y2) for x1,y1,x2,y2 in rectangles]\n",
    "        sides_rgh = [(x2,1,y1,y2) for x1,y1,x2,y2 in rectangles]\n",
    "        sides = sorted(sides_lft + sides_rgh)\n",
    "        \n",
    "        intervals, ans, prev_x = [], 0, sides[0][0]\n",
    "\n",
    "        for x, op_cl, y1, y2 in sides:\n",
    "            ans += merge(intervals) * (x - prev_x)\n",
    "            \n",
    "            if op_cl == 0:\n",
    "                intervals.append((y1,y2))\n",
    "            else:\n",
    "                intervals.remove((y1,y2))     \n",
    "            prev_x = x\n",
    "            \n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "MOD = 1000000007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # 记录左右边界 [x1, x2]\n",
    "        boundaries = []\n",
    "        for rectangle in rectangles:\n",
    "            boundaries.append(rectangle[0])\n",
    "            boundaries.append(rectangle[2])\n",
    "\n",
    "        boundaries.sort()\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, len(boundaries)):\n",
    "            x1, x2 = boundaries[i - 1], boundaries[i]\n",
    "            # 子矩形的水平宽度\n",
    "            width = x2 - x1\n",
    "            if width == 0:\n",
    "                continue\n",
    "\n",
    "            # 找到所有覆盖当前子区间的矩形，并记录其上下边界\n",
    "            lines = list()\n",
    "            for rectangle in rectangles:\n",
    "                if rectangle[0] <= x1 and x2 <= rectangle[2]:\n",
    "                    lines.append((rectangle[1], rectangle[3]))\n",
    "\n",
    "            height = self.count_length(lines)\n",
    "\n",
    "            result += height * width\n",
    "        return result % MOD\n",
    "\n",
    "    @classmethod\n",
    "    def count_length(cls, intervals: List[Tuple[int, int]]):\n",
    "        \"\"\" 计算所有子区间的长度，区间可能重叠\n",
    "        :param intervals:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        intervals.sort()\n",
    "        length, start, end = 0, -1, -1\n",
    "        for interval in intervals:\n",
    "            # 记录新的区间\n",
    "            if interval[0] > end:\n",
    "                # 累加区间长度\n",
    "                length += end - start\n",
    "                # 记录新的区间范围\n",
    "                start, end = interval\n",
    "            # 合并区间\n",
    "            elif interval[1] > end:\n",
    "                end = interval[1]\n",
    "        length += end - start\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        hbound = set()\n",
    "        for rec in rectangles:\n",
    "            hbound.add(rec[1])\n",
    "            hbound.add(rec[3])\n",
    "        hbound = sorted(hbound)\n",
    "        m = len(hbound)\n",
    "        seg = [0] * (m - 1)\n",
    "\n",
    "        sweep = list()\n",
    "        for i, rec in enumerate(rectangles):\n",
    "            sweep.append((rec[0], i, 1))\n",
    "            sweep.append((rec[2], i, -1))\n",
    "        sweep.sort()\n",
    "\n",
    "        ans = i = 0\n",
    "        while i < len(sweep):\n",
    "            j = i\n",
    "            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(sweep):\n",
    "                break\n",
    "            for k in range(i, j + 1):\n",
    "                _, idx, diff = sweep[k]\n",
    "                left, right = rectangles[idx][1], rectangles[idx][3]\n",
    "                for x in range(m - 1):\n",
    "                    if left <= hbound[x] and hbound[x + 1] <= right:\n",
    "                        seg[x] += diff\n",
    "                \n",
    "            cover = 0\n",
    "            for k in range(m - 1):\n",
    "                if seg[k] > 0:\n",
    "                    cover += hbound[k + 1] - hbound[k]\n",
    "            ans += cover * (sweep[j + 1][0] - sweep[j][0])\n",
    "            i = j + 1\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "MOD = 1000000007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # m 个纵坐标最多可以将平行于Y轴的扫描线分成 m - 1 个区间（去掉两端的射线）\n",
    "        vertical_boundaries = set()\n",
    "        for rectangle in rectangles:\n",
    "            vertical_boundaries.add(rectangle[1])\n",
    "            vertical_boundaries.add(rectangle[3])\n",
    "        vertical_boundaries = sorted(vertical_boundaries)\n",
    "\n",
    "        m = len(vertical_boundaries)\n",
    "        horizon_boundaries = list()  # 记录所有的横坐标\n",
    "        for i, rectangle in enumerate(rectangles):\n",
    "            horizon_boundaries.append((rectangle[0], i, 1))\n",
    "            horizon_boundaries.append((rectangle[2], i, -1))\n",
    "        # 将矩形的所有左右边界按从小到大的顺序排序\n",
    "        horizon_boundaries.sort()\n",
    "        # 记录Y轴上每一个线段的状态\n",
    "        cover_times = [0] * (m - 1)\n",
    "        result = 0\n",
    "        i = 0\n",
    "        # 扫描线水平从左向右扫描所有的X坐标\n",
    "        while i < len(horizon_boundaries):\n",
    "            j = i + 1\n",
    "            # 找到第一个不相等的横坐标\n",
    "            while j < len(horizon_boundaries) and horizon_boundaries[i][0] == horizon_boundaries[j][0]:\n",
    "                j += 1\n",
    "            if j == len(horizon_boundaries):\n",
    "                break\n",
    "\n",
    "            # 遍历这 j-1+1 个 x 坐标\n",
    "            for k in range(i, j):\n",
    "                _, index, diff = horizon_boundaries[k]\n",
    "                # 找到这些 x 坐标所对应的上下边界的纵坐标 y1, y2\n",
    "                y1, y2 = rectangles[index][1], rectangles[index][3]\n",
    "                # 遍历所有的纵向线段，线段有两种状态：线段被矩形覆盖；不在矩形覆盖范围内。\n",
    "                for p in range(m - 1):\n",
    "                    # 如果该线段在 [y1, y2] 覆盖范围内，就更新其状态\n",
    "                    if y1 <= vertical_boundaries[p] and vertical_boundaries[p + 1] <= y2:\n",
    "                        cover_times[p] += diff\n",
    "\n",
    "            # 求扫描线上被矩形覆盖的线段之和，也就是高度\n",
    "            height = 0\n",
    "            # 遍历所有的纵向线段\n",
    "            for p in range(m - 1):\n",
    "                # 如果线段它被矩形覆盖，其高度一定是两个相邻线段的差值\n",
    "                if cover_times[p] > 0:\n",
    "                    height += (vertical_boundaries[p + 1] - vertical_boundaries[p])\n",
    "            # 计算扫描线经过范围内被覆盖的面积\n",
    "            result += height * (horizon_boundaries[j][0] - horizon_boundaries[i][0])\n",
    "            result %= MOD\n",
    "            i = j\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "\n",
    "MOD = 1000000007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # m 个纵坐标最多可以将平行于Y轴的扫描线分成 m - 1 个区间（去掉两端的射线）\n",
    "        vertical_boundaries = set()\n",
    "        for rectangle in rectangles:\n",
    "            vertical_boundaries.add(rectangle[1])\n",
    "            vertical_boundaries.add(rectangle[3])\n",
    "        vertical_boundaries = sorted(vertical_boundaries)\n",
    "\n",
    "        m = len(vertical_boundaries)\n",
    "        horizon_boundaries = list()  # 记录所有的横坐标\n",
    "        for i, rectangle in enumerate(rectangles):\n",
    "            horizon_boundaries.append((rectangle[0], i, 1))\n",
    "            horizon_boundaries.append((rectangle[2], i, -1))\n",
    "        # 将矩形的所有左右边界按从小到大的顺序排序\n",
    "        horizon_boundaries.sort()\n",
    "        # 记录Y轴上每一个线段的状态\n",
    "        cover_times = [0] * (m - 1)\n",
    "        result = 0\n",
    "        i = 0\n",
    "        # 扫描线水平从左向右扫描所有的X坐标\n",
    "        while i < len(horizon_boundaries):\n",
    "            j = i\n",
    "            # 找到第一个不相等的横坐标\n",
    "            while j + 1 < len(horizon_boundaries) and horizon_boundaries[i][0] == horizon_boundaries[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(horizon_boundaries):\n",
    "                break\n",
    "\n",
    "            # 遍历这 j-1+1 个 x 坐标\n",
    "            for k in range(i, j + 1):\n",
    "                _, index, diff = horizon_boundaries[k]\n",
    "                # 找到这些 x 坐标所对应的上下边界的纵坐标 y1, y2\n",
    "                y1, y2 = rectangles[index][1], rectangles[index][3]\n",
    "                # 遍历所有的纵向线段，线段有两种状态：线段被矩形覆盖；不在矩形覆盖范围内。\n",
    "                for p in range(m - 1):\n",
    "                    # 如果该线段在 [y1, y2] 覆盖范围内，就更新其状态\n",
    "                    if y1 <= vertical_boundaries[p] and vertical_boundaries[p + 1] <= y2:\n",
    "                        cover_times[p] += diff\n",
    "\n",
    "            # 求扫描线上被矩形覆盖的线段之和，也就是高度\n",
    "            height = 0\n",
    "            # 遍历所有的纵向线段\n",
    "            for p in range(m - 1):\n",
    "                # 如果线段它被矩形覆盖，其高度一定是两个相邻线段的差值\n",
    "                if cover_times[p] > 0:\n",
    "                    height += (vertical_boundaries[p + 1] - vertical_boundaries[p])\n",
    "            # 计算扫描线经过范围内被覆盖的面积\n",
    "            result += height * (horizon_boundaries[j + 1][0] - horizon_boundaries[i][0])\n",
    "            result %= MOD\n",
    "            i = j + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        hbound = set()\n",
    "        for rec in rectangles:\n",
    "            hbound.add(rec[1])\n",
    "            hbound.add(rec[3])\n",
    "        hbound = sorted(hbound)\n",
    "        m = len(hbound)\n",
    "        seg = [0] * (m - 1)\n",
    "\n",
    "        sweep = list()\n",
    "        for i, rec in enumerate(rectangles):\n",
    "            sweep.append((rec[0], i, 1))\n",
    "            sweep.append((rec[2], i, -1))\n",
    "        sweep.sort()\n",
    "        ans = i = 0\n",
    "        while i < len(sweep):\n",
    "            j = i\n",
    "            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(sweep):\n",
    "                break\n",
    "            for k in range(i, j + 1):\n",
    "                _, idx, diff = sweep[k]\n",
    "                low, high = rectangles[idx][1], rectangles[idx][3]\n",
    "                for u in range(m - 1):\n",
    "                    if low <= hbound[u] and hbound[u + 1] <= high:\n",
    "                        seg[u] += diff\n",
    "            cover = 0\n",
    "            for k in range(m - 1):\n",
    "                if seg[k] > 0:\n",
    "                    cover += hbound[k + 1] - hbound[k]\n",
    "            ans += cover * (sweep[j + 1][0] - sweep[j][0])\n",
    "            i = j + 1\n",
    "        return ans % (10 ** 9 + 7)\n",
    "            \n",
    "\n",
    "        # hbound = set()\n",
    "        # for rec in rectangles:\n",
    "        #     hbound.add(rec[1])\n",
    "        #     hbound.add(rec[3])\n",
    "        # hbound = sorted(hbound)\n",
    "        # m = len(hbound)\n",
    "        # seg = [0] * (m - 1)\n",
    "\n",
    "        # sweep = list()\n",
    "        # for i, rec in enumerate(rectangles):\n",
    "        #     sweep.append((rec[0], i, 1))\n",
    "        #     sweep.append((rec[2], i, -1))\n",
    "        # sweep.sort()\n",
    "\n",
    "        # ans = i = 0\n",
    "        # while i < len(sweep):\n",
    "        #     j = i\n",
    "        #     while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "        #         j += 1\n",
    "        #     if j + 1 == len(sweep):\n",
    "        #         break\n",
    "        #     for k in range(i, j + 1):\n",
    "        #         _, idx, diff = sweep[k]\n",
    "        #         left, right = rectangles[idx][1], rectangles[idx][3]\n",
    "        #         for x in range(m - 1):\n",
    "        #             if left <= hbound[x] and hbound[x + 1] <= right:\n",
    "        #                 seg[x] += diff    \n",
    "        #     cover = 0\n",
    "        #     for k in range(m - 1):\n",
    "        #         if seg[k] > 0:\n",
    "        #             cover += hbound[k + 1] - hbound[k]\n",
    "        #     ans += cover * (sweep[j + 1][0] - sweep[j][0])\n",
    "        #     i = j + 1\n",
    "        # return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # Y轴要扫描的范围\n",
    "        vertical_bound = set()\n",
    "        for rectangle in rectangles:\n",
    "            # 下边界\n",
    "            vertical_bound.add(rectangle[1])\n",
    "            # 上边界\n",
    "            vertical_bound.add(rectangle[3])\n",
    "        vertical_bound = sorted(vertical_bound)\n",
    "\n",
    "        m = len(vertical_bound)\n",
    "        # X轴要扫描的范围\n",
    "        sweep = list()\n",
    "        for i, rectangle in enumerate(rectangles):\n",
    "            # 左边界\n",
    "            sweep.append((rectangle[0], i, 1))\n",
    "            # 右边界\n",
    "            sweep.append((rectangle[2], i, -1))\n",
    "\n",
    "        # 将矩形的X轴的边界按照X从小到大排序\n",
    "        sweep.sort()\n",
    "\n",
    "        # cover_times[i] 表示第 i 个线段被矩形覆盖的次数\n",
    "        cover_times = [0] * (m - 1)\n",
    "        result = i = 0\n",
    "\n",
    "        # 遍历所有的X轴的边界\n",
    "        while i < len(sweep):\n",
    "            j = i\n",
    "            # 横坐标相同的左右边界\n",
    "            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(sweep):\n",
    "                break\n",
    "\n",
    "            # 一次性地处理掉[i, j]范围内，一批横坐标相同的左右边界\n",
    "            for k in range(i, j + 1):\n",
    "                _, index, diff = sweep[k]\n",
    "                # 找到这些边界对应的纵坐标\n",
    "                y1, y2 = rectangles[index][1], rectangles[index][3]\n",
    "                # 遍历所有的矩形的纵坐标，如果纵坐标在具有相同X边界的范围内，就更新它的覆盖权重（可能增加也可能减少）\n",
    "                for _i in range(m - 1):\n",
    "                    if y1 <= vertical_bound[_i] and vertical_bound[_i + 1] <= y2:\n",
    "                        cover_times[_i] += diff\n",
    "            print(cover_times)\n",
    "            # Y轴覆盖的线段范围\n",
    "            cover = 0\n",
    "            # 遍历所有的纵坐标\n",
    "            for k in range(m - 1):\n",
    "                if cover_times[k] > 0:\n",
    "                    # 纵坐标上每一段覆盖的范围一定是两个相邻线段的差值\n",
    "                    cover += (vertical_bound[k + 1] - vertical_bound[k])\n",
    "            # 对X轴扫描过的范围进行积分\n",
    "            result += cover * (sweep[j + 1][0] - sweep[i][0])\n",
    "            i = j + 1\n",
    "\n",
    "        return result % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "        self.cnt = 0\n",
    "        self.num = 0\n",
    "        self.leftPoint = 0\n",
    "        self.rightPoint = 0\n",
    "        self.left = None \n",
    "        self.right = None\n",
    "        self.len = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, X):\n",
    "        n = len(X)\n",
    "        self.X = X\n",
    "        self.root = Node(0, n - 1)\n",
    "    \n",
    "    def update(self, root, i, j, val):\n",
    "        if root.start == i and root.end == j:\n",
    "            root.cnt += val\n",
    "        else:\n",
    "            mid = root.start + (root.end - root.start) // 2 \n",
    "            if not root.left:\n",
    "                root.left = Node(root.start, mid)\n",
    "            if not root.right:\n",
    "                root.right = Node(mid + 1, root.end)\n",
    "            if i <= mid:\n",
    "                self.update(root.left, i, min(j, mid), val)\n",
    "            if j > mid:\n",
    "                self.update(root.right, max(i, mid + 1), j, val)\n",
    "        self.push_up(root)\n",
    "    \n",
    "    def push_up(self, root):\n",
    "        mid = root.start + (root.end - root.start) // 2 \n",
    "        if not root.left:\n",
    "            root.left = Node(root.start, mid)\n",
    "        if not root.right:\n",
    "            root.right = Node(mid + 1, root.end)\n",
    "        if root.cnt > 0:\n",
    "            root.len = self.X[root.end + 1] - self.X[root.start]\n",
    "            root.num = 1 \n",
    "            root.leftPoint = 1 \n",
    "            root.rightPoint = 1\n",
    "        elif root.start == root.end:\n",
    "            root.num = 0\n",
    "            root.leftPoint = 0\n",
    "            root.rightPoint = 0 \n",
    "            root.len = 0\n",
    "        else:\n",
    "            root.leftPoint = root.left.leftPoint\n",
    "            root.rightPoint = root.right.leftPoint\n",
    "            root.num = root.left.cnt + root.right.cnt - (root.left.rightPoint & root.right.leftPoint)\n",
    "            root.len = root.left.len + root.right.len \n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        X = set()\n",
    "        event = []\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            event.append([y1, 1, x1, x2])\n",
    "            event.append([y2, - 1, x1, x2])\n",
    "            X.add(x1)\n",
    "            X.add(x2)\n",
    "        X = sorted(X)\n",
    "        Xi = {x : i for i, x in enumerate(X)}\n",
    "        sg = SegmentTree(X)\n",
    "        event.sort()\n",
    "        length = 0\n",
    "        area = 0\n",
    "        prey = event[0][0]\n",
    "        for y, val, x1, x2 in event:\n",
    "            prex = sg.root.len \n",
    "            area += prex * (y - prey)\n",
    "            length += (y - prey) * 2 * sg.root.num \n",
    "            sg.update(sg.root, Xi[x1], Xi[x2] - 1, val)\n",
    "            length += abs(sg.root.len - prex)\n",
    "            prey = y \n",
    "        print(length)\n",
    "        return area % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "        Xi = {x : i for i, x in enumerate(X)}\n",
    "        sg = SegmentTree(X)\n",
    "        event.sort()\n",
    "        length = 0\n",
    "        area = 0\n",
    "        prey = event[0][0]\n",
    "        for y, val, x1, x2 in event:\n",
    "            curX = sg.root.len \n",
    "            area += (y - prey) * curX\n",
    "            length += (y - prey) * 2 * sg.root.num \n",
    "            sg.update(sg.root, Xi[x1], Xi[x2] - 1, val)\n",
    "            length += abs(sg.root.len - curX)\n",
    "            prey = y \n",
    "            # print(y, prey)\n",
    "        print(length)\n",
    "        return area % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.l = self.r = 0\n",
    "        self.cnt = self.length = 0\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, nums):\n",
    "        n = len(nums) - 1\n",
    "        self.nums = nums\n",
    "        self.tr = [Node() for _ in range(n << 2)]\n",
    "        self.build(1, 0, n - 1)\n",
    "\n",
    "    def build(self, u, l, r):\n",
    "        self.tr[u].l, self.tr[u].r = l, r\n",
    "        if l != r:\n",
    "            mid = (l + r) >> 1\n",
    "            self.build(u << 1, l, mid)\n",
    "            self.build(u << 1 | 1, mid + 1, r)\n",
    "\n",
    "    def modify(self, u, l, r, k):\n",
    "        if self.tr[u].l >= l and self.tr[u].r <= r:\n",
    "            self.tr[u].cnt += k\n",
    "        else:\n",
    "            mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "            if l <= mid:\n",
    "                self.modify(u << 1, l, r, k)\n",
    "            if r > mid:\n",
    "                self.modify(u << 1 | 1, l, r, k)\n",
    "        self.pushup(u)\n",
    "\n",
    "    def pushup(self, u):\n",
    "        if self.tr[u].cnt:\n",
    "            self.tr[u].length = self.nums[self.tr[u].r + 1] - \\\n",
    "                self.nums[self.tr[u].l]\n",
    "        elif self.tr[u].l == self.tr[u].r:\n",
    "            self.tr[u].length = 0\n",
    "        else:\n",
    "            self.tr[u].length = self.tr[u << 1].length + \\\n",
    "                self.tr[u << 1 | 1].length\n",
    "\n",
    "    @property\n",
    "    def length(self):\n",
    "        return self.tr[1].length\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        segs = []\n",
    "        alls = set()\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            # 矩形左侧线段\n",
    "            segs.append((x1, y1, y2, 1))\n",
    "            # 矩形右侧线段\n",
    "            segs.append((x2, y1, y2, -1))\n",
    "            # 存储所有出现过的 Y 坐标\n",
    "            alls.update([y1, y2])\n",
    "\n",
    "        segs.sort()\n",
    "\n",
    "        # Y 坐标排序，离散化\n",
    "        alls = sorted(alls)\n",
    "        tree = SegmentTree(alls)\n",
    "        m = {v: i for i, v in enumerate(alls)}\n",
    "        ans = 0\n",
    "        for i, (x, y1, y2, k) in enumerate(segs):\n",
    "            if i:\n",
    "                # Y 坐标被覆盖的长度 乘以 相邻横坐标之差\n",
    "                ans += tree.length * (x - segs[i - 1][0])\n",
    "            tree.modify(1, m[y1], m[y2] - 1, k)\n",
    "        ans %= int(1e9 + 7)\n",
    "        return ans\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.l = self.r = 0\n",
    "        self.cnt = self.length = 0\n",
    "\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, nums):\n",
    "        n = len(nums) - 1\n",
    "        self.nums = nums\n",
    "        self.tr = [Node() for _ in range(n << 2)]\n",
    "        self.build(1, 0, n - 1)\n",
    "\n",
    "    def build(self, u, l, r):\n",
    "        self.tr[u].l, self.tr[u].r = l, r\n",
    "        if l != r:\n",
    "            mid = (l + r) >> 1\n",
    "            self.build(u << 1, l, mid)\n",
    "            self.build(u << 1 | 1, mid + 1, r)\n",
    "\n",
    "    def modify(self, u, l, r, k):\n",
    "        if self.tr[u].l >= l and self.tr[u].r <= r:\n",
    "            self.tr[u].cnt += k\n",
    "        else:\n",
    "            mid = (self.tr[u].l + self.tr[u].r) >> 1\n",
    "            if l <= mid:\n",
    "                self.modify(u << 1, l, r, k)\n",
    "            if r > mid:\n",
    "                self.modify(u << 1 | 1, l, r, k)\n",
    "        self.pushup(u)\n",
    "\n",
    "    def pushup(self, u):\n",
    "        if self.tr[u].cnt:\n",
    "            self.tr[u].length = self.nums[self.tr[u].r + 1] - \\\n",
    "                self.nums[self.tr[u].l]\n",
    "        elif self.tr[u].l == self.tr[u].r:\n",
    "            self.tr[u].length = 0\n",
    "        else:\n",
    "            self.tr[u].length = self.tr[u << 1].length + \\\n",
    "                self.tr[u << 1 | 1].length\n",
    "\n",
    "    @property\n",
    "    def length(self):\n",
    "        return self.tr[1].length\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        segs = []\n",
    "        alls = set()\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            # 矩形左侧线段\n",
    "            segs.append((x1, y1, y2, 1))\n",
    "            # 矩形右侧线段\n",
    "            segs.append((x2, y1, y2, -1))\n",
    "            # 存储所有出现过的 Y 坐标\n",
    "            alls.update([y1, y2])\n",
    "\n",
    "        segs.sort()\n",
    "\n",
    "        # Y 坐标排序，离散化\n",
    "        alls = sorted(alls)\n",
    "        tree = SegmentTree(alls)\n",
    "        m = {v: i for i, v in enumerate(alls)}\n",
    "        ans = 0\n",
    "        for i, (x, y1, y2, k) in enumerate(segs):\n",
    "            if i:\n",
    "                # Y 坐标被覆盖的长度 乘以 相邻横坐标之差\n",
    "                ans += tree.length * (x - segs[i - 1][0])\n",
    "            tree.modify(1, m[y1], m[y2] - 1, k)\n",
    "        ans %= int(1e9 + 7)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        # Y轴要扫描的范围\n",
    "        vertical_bound = set()\n",
    "        for rectangle in rectangles:\n",
    "            # 下边界\n",
    "            vertical_bound.add(rectangle[1])\n",
    "            # 上边界\n",
    "            vertical_bound.add(rectangle[3])\n",
    "        vertical_bound = sorted(vertical_bound)\n",
    "\n",
    "        m = len(vertical_bound)\n",
    "        # 记录所有的左右边界\n",
    "        sweep = list()\n",
    "        for i, rectangle in enumerate(rectangles):\n",
    "            # 左边界，遇到覆盖次数加1\n",
    "            sweep.append((rectangle[0], i, 1))\n",
    "            # 右边界，遇到覆盖次数减1\n",
    "            sweep.append((rectangle[2], i, -1))\n",
    "\n",
    "        # 将矩形的所有左右边界按从小到大的顺序排序\n",
    "        sweep.sort()\n",
    "\n",
    "        print(vertical_bound)\n",
    "        print(sweep)\n",
    "\n",
    "        # cover_times[i] 表示第 i 个线段被矩形覆盖的次数\n",
    "        cover_times = [0] * (m - 1)\n",
    "        result = 0\n",
    "        i = 0\n",
    "        # 遍历所有的X轴的边界\n",
    "        while i < len(sweep):\n",
    "            j = i\n",
    "            # 横坐标相同的左右边界\n",
    "            while j + 1 < len(sweep) and sweep[i][0] == sweep[j + 1][0]:\n",
    "                j += 1\n",
    "            if j + 1 == len(sweep):\n",
    "                break\n",
    "\n",
    "            # 一次性地处理掉[i, j]范围内，一批横坐标相同的左右边界\n",
    "            for k in range(i, j + 1):\n",
    "                _, index, diff = sweep[k]\n",
    "                # 找到这些边界对应的纵坐标\n",
    "                y1, y2 = rectangles[index][1], rectangles[index][3]\n",
    "                # 遍历扫描线上所有被上下边界覆盖的线段\n",
    "                print(\"k=%s\" % k)\n",
    "                for p in range(m - 1):\n",
    "                    # 如果纵坐标在具有相同X边界的范围内，就更新它的覆盖次数\n",
    "                    print(\"[%s, %s]\" % (p, p + 1))\n",
    "                    if y1 <= vertical_bound[p] and vertical_bound[p + 1] <= y2:\n",
    "                        cover_times[p] += diff\n",
    "            print(cover_times)\n",
    "\n",
    "            # 扫描线上被矩形覆盖的线段之和\n",
    "            covered_length = 0\n",
    "            # 遍历扫描线上所有被矩形覆盖的线段\n",
    "            for p in range(m - 1):\n",
    "                if cover_times[p] > 0:\n",
    "                    # 纵坐标上每一段覆盖的范围一定是两个相邻线段的差值\n",
    "                    covered_length += (vertical_bound[p + 1] - vertical_bound[p])\n",
    "            # 计算扫描线经过范围内被覆盖的面积\n",
    "            result += covered_length * (sweep[j + 1][0] - sweep[i][0])\n",
    "            i = j + 1\n",
    "\n",
    "        return result % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.coverLen = 0\n",
    "        self.cover = 0\n",
    "\n",
    "class SegmentTree():\n",
    "    maxNode = 201\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    def createNode(self,node):\n",
    "        if node.left == None:\n",
    "            node.left = Node()\n",
    "        if node.right == None:\n",
    "            node.right = Node()\n",
    "    def update(self,left,right,value,index2Y):\n",
    "        self._update(self.root,1,self.maxNode,left,right,value,index2Y)\n",
    "    def _update(self, node, start, end, left,right, value,index2Y):\n",
    "        \n",
    "        self.createNode(node)\n",
    "        if left<=start and end <= right:\n",
    "            # print(start,end,left,right)\n",
    "            node.cover+=value\n",
    "            self.pushUp(node, start, end, index2Y)\n",
    "            return\n",
    "        mid = start + (end -start)//2\n",
    "        if left<=mid:\n",
    "            self._update(node.left,start,mid,left,right,value,index2Y)\n",
    "        if right>=mid+1:\n",
    "            self._update(node.right,mid+1,end,left,right,value,index2Y)\n",
    "        self.pushUp(node,start,end,index2Y)\n",
    "    \n",
    "    def pushUp(self,node,start,end,index2Y):\n",
    "        if(node.cover > 0):\n",
    "            node.coverLen = index2Y.get(end+1) - index2Y.get(start)\n",
    "        elif (start!=end):\n",
    "            node.coverLen = node.left.coverLen + node.right.coverLen\n",
    "        else:\n",
    "            node.coverLen = 0\n",
    "    def query(self,):\n",
    "        return self.root.coverLen\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        ySet = SortedSet()\n",
    "        y2Index = {}\n",
    "        index2Y = {}\n",
    "        xList = []\n",
    "        for x1,y1,x2,y2 in rectangles:\n",
    "            xList.append([x1,y1,y2,1])\n",
    "            xList.append([x2,y1,y2,-1])\n",
    "            ySet.add(y1)\n",
    "            ySet.add(y2)\n",
    "        count = 1\n",
    "        for y in ySet:\n",
    "            y2Index[y] = count\n",
    "            index2Y[count] = y\n",
    "            count+=1\n",
    "        \n",
    "        xList.sort()\n",
    "        segmentTree = SegmentTree()\n",
    "        ans = 0\n",
    "        MOD = 10**9+7\n",
    "        for i in range(len(xList)-1):\n",
    "            cur = xList[i]\n",
    "            left = y2Index.get(cur[1])\n",
    "            right = y2Index.get(cur[2])\n",
    "            segmentTree.update(left,right-1,cur[3],index2Y)\n",
    "     \n",
    "            ans = (ans + segmentTree.query() * (xList[i+1][0] - cur[0])) % MOD\n",
    "        \n",
    "        return ans %MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.coverLen = 0\n",
    "        self.cover = 0\n",
    "\n",
    "class SegmentTree():\n",
    "    maxNode = 201\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    def createNode(self,node):\n",
    "        if node.left == None:\n",
    "            node.left = Node()\n",
    "        if node.right == None:\n",
    "            node.right = Node()\n",
    "    def update(self,left,right,value,index2Y):\n",
    "        self._update(self.root,1,self.maxNode,left,right,value,index2Y)\n",
    "    def _update(self, node, start, end, left,right, value,index2Y):\n",
    "        self.createNode(node)\n",
    "        if left<=start and end <= right:\n",
    "            node.cover+=value\n",
    "            self.pushUp(node, start, end, index2Y)\n",
    "            return\n",
    "        mid = start + (end -start)//2\n",
    "        if left<=mid:\n",
    "            self._update(node.left,start,mid,left,right,value,index2Y)\n",
    "        if right>=mid+1:\n",
    "            self._update(node.right,mid+1,end,left,right,value,index2Y)\n",
    "        self.pushUp(node,start,end,index2Y)\n",
    "    \n",
    "    def pushUp(self,node,start,end,index2Y):\n",
    "        if(node.cover > 0):\n",
    "            node.coverLen = index2Y.get(end + 1) - index2Y.get(start)\n",
    "        elif (start!=end):\n",
    "            node.coverLen = node.left.coverLen + node.right.coverLen\n",
    "        else:\n",
    "            node.coverLen = 0\n",
    "    def query(self,):\n",
    "        return self.root.coverLen\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def rectangleArea(self, rectangles: List[List[int]]) -> int:\n",
    "        ySet = SortedSet()\n",
    "        y2Index = {}\n",
    "        index2Y = {}\n",
    "        xList = []\n",
    "        for x1,y1,x2,y2 in rectangles:\n",
    "            xList.append([x1,y1,y2,1])\n",
    "            xList.append([x2,y1,y2,-1])\n",
    "            ySet.add(y1)\n",
    "            ySet.add(y2)\n",
    "        count = 1\n",
    "        for y in ySet:\n",
    "            y2Index[y] = count\n",
    "            index2Y[count] = y\n",
    "            count+=1\n",
    "        \n",
    "        xList.sort()\n",
    "        segmentTree = SegmentTree()\n",
    "        ans = 0\n",
    "        MOD = 10**9+7\n",
    "        for i in range(len(xList)-1):\n",
    "            cur = xList[i]\n",
    "            left = y2Index.get(cur[1])\n",
    "            right = y2Index.get(cur[2])\n",
    "            segmentTree.update(left,right-1,cur[3],index2Y)\n",
    "     \n",
    "            ans = (ans + segmentTree.query() * (xList[i+1][0] - cur[0])) % MOD\n",
    "        \n",
    "        return ans %MOD\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
